<!DOCTYPE HTML>
<html lang="zh-CN" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title> Section 4.6 - PurpleDragonBookAnswer</title>


        <!-- Custom HTML head -->
        
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="Purple Dragon Book Answer Online Edition">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="../../favicon.svg">
        <link rel="shortcut icon" href="../../favicon.png">
        <link rel="stylesheet" href="../../css/variables.css">
        <link rel="stylesheet" href="../../css/general.css">
        <link rel="stylesheet" href="../../css/chrome.css">
        <link rel="stylesheet" href="../../css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="../../fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="../../highlight.css">
        <link rel="stylesheet" href="../../tomorrow-night.css">
        <link rel="stylesheet" href="../../ayu-highlight.css">

        <!-- Custom theme stylesheets -->

    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "../../";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded "><a href="../../preface.html"><strong aria-hidden="true">1.</strong> Preface</a></li><li class="chapter-item expanded "><a href="../../ch01/ch01.html"><strong aria-hidden="true">2.</strong> Chapter 1</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch01/1.1/1.1.html"><strong aria-hidden="true">2.1.</strong> Section 1.1</a></li><li class="chapter-item expanded "><a href="../../ch01/1.3/1.3.html"><strong aria-hidden="true">2.2.</strong> Section 1.3</a></li><li class="chapter-item expanded "><a href="../../ch01/1.6/1.6.html"><strong aria-hidden="true">2.3.</strong> Section 1.6</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch02/ch02.html"><strong aria-hidden="true">3.</strong> Chapter 2</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch02/key-point/key-point.html"><strong aria-hidden="true">3.1.</strong> KeyPoints</a></li><li class="chapter-item expanded "><a href="../../ch02/2.2/2.2.html"><strong aria-hidden="true">3.2.</strong> Section 2.2</a></li><li class="chapter-item expanded "><a href="../../ch02/2.3/2.3.html"><strong aria-hidden="true">3.3.</strong> Section 2.3</a></li><li class="chapter-item expanded "><a href="../../ch02/2.4/2.4.html"><strong aria-hidden="true">3.4.</strong> Section 2.4</a></li><li class="chapter-item expanded "><a href="../../ch02/2.6/2.6.html"><strong aria-hidden="true">3.5.</strong> Section 2.6</a></li><li class="chapter-item expanded "><a href="../../ch02/2.8/2.8.html"><strong aria-hidden="true">3.6.</strong> Section 2.8</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch03/ch03.html"><strong aria-hidden="true">4.</strong> Chapter 3</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch03/key-point/key-point.html"><strong aria-hidden="true">4.1.</strong> KeyPoints</a></li><li class="chapter-item expanded "><a href="../../ch03/3.1/3.1.html"><strong aria-hidden="true">4.2.</strong> Section 3.1</a></li><li class="chapter-item expanded "><a href="../../ch03/3.3/3.3.html"><strong aria-hidden="true">4.3.</strong> Section 3.3</a></li><li class="chapter-item expanded "><a href="../../ch03/3.4/3.4.html"><strong aria-hidden="true">4.4.</strong> Section 3.4</a></li><li class="chapter-item expanded "><a href="../../ch03/3.5/3.5.html"><strong aria-hidden="true">4.5.</strong> Section 3.5</a></li><li class="chapter-item expanded "><a href="../../ch03/3.6/3.6.html"><strong aria-hidden="true">4.6.</strong> Section 3.6</a></li><li class="chapter-item expanded "><a href="../../ch03/3.7/3.7.html"><strong aria-hidden="true">4.7.</strong> Section 3.7</a></li><li class="chapter-item expanded "><a href="../../ch03/3.8/3.8.html"><strong aria-hidden="true">4.8.</strong> Section 3.8</a></li><li class="chapter-item expanded "><a href="../../ch03/3.9/3.9.html"><strong aria-hidden="true">4.9.</strong> Section 3.9</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch04/ch04.html"><strong aria-hidden="true">5.</strong> Chapter 4</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch04/key-point/key-point.html"><strong aria-hidden="true">5.1.</strong> KeyPoints</a></li><li class="chapter-item expanded "><a href="../../ch04/4.2/4.2.html"><strong aria-hidden="true">5.2.</strong> Section 4.2</a></li><li class="chapter-item expanded "><a href="../../ch04/4.3/4.3.html"><strong aria-hidden="true">5.3.</strong> Section 4.3</a></li><li class="chapter-item expanded "><a href="../../ch04/4.4/4.4.html"><strong aria-hidden="true">5.4.</strong> Section 4.4</a></li><li class="chapter-item expanded "><a href="../../ch04/4.5/4.5.html"><strong aria-hidden="true">5.5.</strong> Section 4.5</a></li><li class="chapter-item expanded "><a href="../../ch04/4.6/4.6.html" class="active"><strong aria-hidden="true">5.6.</strong> Section 4.6</a></li><li class="chapter-item expanded "><a href="../../ch04/4.7/4.7.html"><strong aria-hidden="true">5.7.</strong> Section 4.7</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch05/ch05.html"><strong aria-hidden="true">6.</strong> Chapter 5</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch05/5.1/5.1.html"><strong aria-hidden="true">6.1.</strong> Section 5.1</a></li><li class="chapter-item expanded "><a href="../../ch05/5.2/5.2.html"><strong aria-hidden="true">6.2.</strong> Section 5.2</a></li><li class="chapter-item expanded "><a href="../../ch05/5.3/5.3.html"><strong aria-hidden="true">6.3.</strong> Section 5.3</a></li><li class="chapter-item expanded "><a href="../../ch05/5.4/5.4.html"><strong aria-hidden="true">6.4.</strong> Section 5.4</a></li><li class="chapter-item expanded "><a href="../../ch05/5.5/5.5.html"><strong aria-hidden="true">6.5.</strong> Section 5.5</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch06/ch06.html"><strong aria-hidden="true">7.</strong> Chapter 6</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch06/6.1/6.1.html"><strong aria-hidden="true">7.1.</strong> Section 6.1</a></li><li class="chapter-item expanded "><a href="../../ch06/6.2/6.2.html"><strong aria-hidden="true">7.2.</strong> Section 6.2</a></li><li class="chapter-item expanded "><a href="../../ch06/6.3/6.3.html"><strong aria-hidden="true">7.3.</strong> Section 6.3</a></li><li class="chapter-item expanded "><a href="../../ch06/6.4/6.4.html"><strong aria-hidden="true">7.4.</strong> Section 6.4</a></li><li class="chapter-item expanded "><a href="../../ch06/6.5/6.5.html"><strong aria-hidden="true">7.5.</strong> Section 6.5</a></li><li class="chapter-item expanded "><a href="../../ch06/6.6/6.6.html"><strong aria-hidden="true">7.6.</strong> Section 6.6</a></li><li class="chapter-item expanded "><a href="../../ch06/6.7/6.7.html"><strong aria-hidden="true">7.7.</strong> Section 6.7</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch07/ch07.html"><strong aria-hidden="true">8.</strong> Chapter 7</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch07/7.2/7.2.html"><strong aria-hidden="true">8.1.</strong> Section 7.2</a></li><li class="chapter-item expanded "><a href="../../ch07/7.3/7.3.html"><strong aria-hidden="true">8.2.</strong> Section 7.3</a></li><li class="chapter-item expanded "><a href="../../ch07/7.3/7.4.html"><strong aria-hidden="true">8.3.</strong> Section 7.4</a></li><li class="chapter-item expanded "><a href="../../ch07/7.5/7.5.html"><strong aria-hidden="true">8.4.</strong> Section 7.5</a></li><li class="chapter-item expanded "><a href="../../ch07/7.6/7.6.html"><strong aria-hidden="true">8.5.</strong> Section 7.6</a></li><li class="chapter-item expanded "><a href="../../ch07/7.7/7.7.html"><strong aria-hidden="true">8.6.</strong> Section 7.7</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch08/ch08.html"><strong aria-hidden="true">9.</strong> Chapter 8</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch08/8.2/8.2.html"><strong aria-hidden="true">9.1.</strong> Section 8.2</a></li><li class="chapter-item expanded "><a href="../../ch08/8.3/8.3.html"><strong aria-hidden="true">9.2.</strong> Section 8.3</a></li><li class="chapter-item expanded "><a href="../../ch08/8.4/8.4.html"><strong aria-hidden="true">9.3.</strong> Section 8.4</a></li><li class="chapter-item expanded "><a href="../../ch08/8.5/8.5.html"><strong aria-hidden="true">9.4.</strong> Section 8.5</a></li></ol></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">PurpleDragonBookAnswer</h1>

                    <div class="right-buttons">
                        <a href="../../print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="46-节的练习"><a class="header" href="#46-节的练习">4.6 节的练习</a></h1>
<h3 id="461"><a class="header" href="#461">4.6.1</a></h3>
<p>描述下列文法的所有可行前缀</p>
<ol>
<li>练习4.2.2-1的文法 S-&gt;0S1|01</li>
<li>！ 练习4.2.1的文法 S-&gt;SS+|SS*|a</li>
<li>！ 练习4.2.2-3的文法 S-&gt;S(S)S|ε</li>
</ol>
<h4 id="解答"><a class="header" href="#解答">解答</a></h4>
<p>以下提取左公因子和消除左递归后的文法均由练习 4.3.2 得到</p>
<ol>
<li>
<p>提取左公因子和消除左递归后的增广文法</p>
<pre><code> 0) S' -&gt; S
 1) S -&gt; 0 A
 2) A -&gt; 0 A 1
 3) A -&gt; 1
</code></pre>
<p>LR(0) 自动机如下：</p>
<p><img src="./assets/4.6.1-1.gif" alt="4 6 1-1" /></p>
<p>可行前缀为 <code>0+A?1?</code></p>
</li>
<li>
<p>提取左公因子和消除左递归后的增广文法</p>
<pre><code> 0) S' -&gt; S
 1) S -&gt; a B
 2) B -&gt; a B A B
 3) B -&gt; ε
 4) A -&gt; +
 5) A -&gt; *
</code></pre>
<p>LR(0) 自动机如下：</p>
<p><img src="./assets/4.6.1-2.gif" alt="4 6 1-2" /></p>
<p>可行前缀为 <code>aB?|aaa*(BAa+)*(B|B+|B*|BA|BAB)?</code>，注意到B+和B*中的+和*都是文法中的非终结符。</p>
</li>
<li>
<p>提取左公因子和消除左递归后的增广文法</p>
<pre><code> 0) S' -&gt; S
 1) S -&gt; A
 2) A -&gt; (S) S A
 3) A -&gt; ε
</code></pre>
<p>LR(0) 自动机如下：</p>
<p><img src="./assets/4.6.1-3.gif" alt="4 6 1-3" /></p>
<p>DFA的转移很复杂，不归纳正则形式的活前缀。</p>
</li>
</ol>
<h3 id="462"><a class="header" href="#462">4.6.2</a></h3>
<p>为练习4.2.1中的（增广）文法构造SLR项集。计算这些项集的GOTO函数。给出这个函数的语法分析表。这个文法是SLR文法吗？</p>
<h4 id="解答-1"><a class="header" href="#解答-1">解答</a></h4>
<p>分析4.6.1-2的文法。该文法的项集和 GOTO 函数见 4.6.1-2</p>
<p>FOLLOW 函数如下：</p>
<pre><code>FOLLOW(S) = [$]
FOLLOW(A) = [a, $]
FOLLOW(B) = [+, * ,$]
</code></pre>
<p>语法分析表如下：</p>
<table>
    <thead>
        <tr>
            <th rowspan="2">状态</th>
            <th colspan="4">ACTION</th>
            <th colspan="3">GOTO</th>
        </tr>
        <tr>
            <th>a</th>
            <th>+</th>
            <th>*</th>
            <th>$</th>
            <th>S</th>
            <th>A</th>
            <th>B</th>
        </tr>
    </thead>
    <tbody>
        <tr>
            <td>0</td>
            <td>s2</td>
            <td></td>
            <td></td>
            <td></td>
            <td>s1</td>
            <td></td>
            <td></td>
        </tr>
        <tr>
            <td>1</td>
            <td></td>
            <td></td>
            <td></td>
            <td>acc</td>
            <td></td>
            <td></td>
            <td></td>
        </tr>
        <tr>
            <td>2</td>
            <td>s4</td>
            <td>r3</td>
            <td>r3</td>
            <td>r3</td>
            <td></td>
            <td></td>
            <td>s3</td>
        </tr>
        <tr>
            <td>3</td>
            <td></td>
            <td></td>
            <td></td>
            <td>r1</td>
            <td></td>
            <td></td>
            <td></td>
        </tr>
        <tr>
            <td>4</td>
            <td>s4</td>
            <td>r3</td>
            <td>r3</td>
            <td>r3</td>
            <td></td>
            <td></td>
            <td>s5</td>
        </tr>
        <tr>
            <td>5</td>
            <td></td>
            <td>s7</td>
            <td>s8</td>
            <td></td>
            <td></td>
            <td>s6</td>
            <td></td>
        </tr>
        <tr>
            <td>6</td>
            <td>s4</td>
            <td>r3</td>
            <td>r3</td>
            <td>r3</td>
            <td></td>
            <td></td>
            <td>s9</td>
        </tr>
        <tr>
            <td>7</td>
            <td>r4</td>
            <td></td>
            <td></td>
            <td>r4</td>
            <td></td>
            <td></td>
            <td></td>
        </tr>
        <tr>
            <td>8</td>
            <td>r5</td>
            <td></td>
            <td></td>
            <td>r5</td>
            <td></td>
            <td></td>
            <td></td>
        </tr>
        <tr>
            <td>9</td>
            <td></td>
            <td>r2</td>
            <td>r2</td>
            <td>r2</td>
            <td></td>
            <td></td>
            <td></td>
        </tr>
    </tbody>
</table>
<p>无冲突，这显然是一个 SLR 文法</p>
<h3 id="463"><a class="header" href="#463">4.6.3</a></h3>
<p>利用练习4.6.2得到的语法分析表，给出处理输入aa*a+时的各个动作。</p>
<h4 id="解答-2"><a class="header" href="#解答-2">解答</a></h4>
<table>
    <thead>
        <tr>
            <th></th>
            <th>栈</th>
            <th>符号</th>
            <th>输入</th>
            <th>动作</th>
        </tr>
    </thead>
    <tbody>
        <tr>
            <td>1)</td>
            <td>0</td>
            <td></td>
            <td>aa*a+$</td>
            <td>移入</td>
        </tr>
        <tr>
            <td>2)</td>
            <td>02</td>
            <td>a</td>
            <td>a*a+$</td>
            <td>移入</td>
        </tr>
        <tr>
            <td>3)</td>
            <td>024</td>
            <td>aa</td>
            <td>*a+$</td>
            <td>根据 B -> ε 规约</td>
        </tr>
        <tr>
            <td>4)</td>
            <td>0245</td>
            <td>aaB</td>
            <td>*a+$</td>
            <td>移入</td>
        </tr>
        <tr>
            <td>5)</td>
            <td>02458</td>
            <td>aaB*</td>
            <td>a+$</td>
            <td>根据 A -> * 规约</td>
        </tr>
        <tr>
            <td>6)</td>
            <td>02456</td>
            <td>aaBA</td>
            <td>a+$</td>
            <td>移入</td>
        </tr>
        <tr>
            <td>7)</td>
            <td>024564</td>
            <td>aaBAa</td>
            <td>+$</td>
            <td>根据 B -> ε 规约</td>
        </tr>
        <tr>
            <td>8)</td>
            <td>0245645</td>
            <td>aaBAaB</td>
            <td>+$</td>
            <td>移入</td>
        </tr>
        <tr>
            <td>9)</td>
            <td>02456457</td>
            <td>aaBAaB+</td>
            <td>$</td>
            <td>根据 A -> + 规约</td>
        </tr>
        <tr>
            <td>9)</td>
            <td>02456456</td>
            <td>aaBAaBA</td>
            <td>$</td>
            <td>根据 B -> ε 规约</td>
        </tr>
        <tr>
            <td>10)</td>
            <td>024564569</td>
            <td>aaBAaBAB</td>
            <td>$</td>
            <td>根据 B -> aBAB 规约</td>
        </tr>
        <tr>
            <td>11)</td>
            <td>024569</td>
            <td>aaBAB</td>
            <td>$</td>
            <td>根据 B -> aBAB 规约</td>
        </tr>
        <tr>
            <td>12)</td>
            <td>023</td>
            <td>aB</td>
            <td>$</td>
            <td>根据 S -> aB 规约</td>
        </tr>
        <tr>
            <td>13)</td>
            <td>01</td>
            <td>S</td>
            <td>$</td>
            <td>接受</td>
        </tr>
    </tbody>
</table>
<h3 id="464"><a class="header" href="#464">4.6.4</a></h3>
<p>对于练习4.2.2-1~4.2.2-7中的各个（增广）文法：</p>
<ol>
<li>构造SLR项集和他们的GOTO函数</li>
<li>指出你的项集中的所有动作冲突</li>
<li>如果存在SLR语法分析表，构造出这个语法分析表</li>
</ol>
<h4 id="2"><a class="header" href="#2">2)</a></h4>
<p>增广文法G2': </p>
<pre><code>0) S' -&gt; S
1) S -&gt; +SS
2) S -&gt; *SS
3) S -&gt; a
</code></pre>
<p>LR(0) 自动机如下：</p>
<p><img src="./assets/4.6.4-2.png" alt="4 6 4-2" /></p>
<p>Follow函数如下：</p>
<pre><code>Follow(S) = [$, +, *, a]
</code></pre>
<p>SLR语法分析表如下：</p>
<table>
    <thead>
        <tr>
            <th rowspan="2">状态</th>
            <th colspan="4">ACTION</th>
            <th colspan="1">GOTO</th>
        </tr>
        <tr>
            <th>a</th>
            <th>+</th>
            <th>*</th>
            <th>$</th>
            <th>S</th>
        </tr>
    </thead>
    <tbody>
        <tr>
            <td>0</td>
            <td>s4</td>
            <td>s2</td>
            <td>s3</td>
            <td></td>
            <td>1</td>
        </tr>
        <tr>
            <td>1</td>
            <td></td>
            <td></td>
            <td></td>
            <td>acc</td>
            <td></td>
        </tr>
        <tr>
            <td>2</td>
            <td>s4</td>
            <td>s2</td>
            <td>s3</td>
            <td></td>
            <td>5</td>
        </tr>
        <tr>
            <td>3</td>
            <td>s4</td>
            <td>s2</td>
            <td>s3</td>
            <td></td>
            <td>6</td>
        </tr>
        <tr>
            <td>4</td>
            <td>r3</td>
            <td>r3</td>
            <td>r3</td>
            <td>r3</td>
            <td></td>
        </tr>
        <tr>
            <td>5</td>
            <td>s4</td>
            <td>s2</td>
            <td>s3</td>
            <td></td>
            <td>7</td>
        </tr>
        <tr>
            <td>6</td>
            <td>s4</td>
            <td>s2</td>
            <td>s3</td>
            <td></td>
            <td>8</td>
        </tr>
        <tr>
            <td>7</td>
            <td>r1</td>
            <td>r1</td>
            <td>r1</td>
            <td>r2</td>
            <td></td>
        </tr>
        <tr>
            <td>8</td>
            <td>r2</td>
            <td>r2</td>
            <td>r2</td>
            <td>r2</td>
            <td></td>
        </tr>
    </tbody>
</table>
<p>不存在s/r冲突，也不存在r/r冲突，故文法G2'属于SLR文法。</p>
<h4 id="5"><a class="header" href="#5">5)</a></h4>
<p>增广文法G5': </p>
<pre><code>0) S' -&gt; S
1) S -&gt; (L)
2) S -&gt; a
3) L -&gt; SA
4) A -&gt; ,SA
5) A -&gt; ε
</code></pre>
<p>LR(0)自动机如下：</p>
<p><img src="./assets/4.6.4-5.png" alt="4 6 4-5" /></p>
<p>Follow函数如下：</p>
<pre><code>Follow(S) = [$, \,, )]
Follow(L) = [)]
Follow(A) = [)]
</code></pre>
<table>
    <thead>
        <tr>
            <th rowspan="2">状态</th>
            <th colspan="5">ACTION</th>
            <th colspan="3">GOTO</th>
        </tr>
        <tr>
            <th>(</th>
            <th>a</th>
            <th>,</th>
            <th>)</th>
            <th>$</th>
            <th>S</th>
            <th>L</th>
            <th>A</th>
        </tr>
    </thead>
    <tbody>
        <tr>
            <td>0</td>
            <td>s2</td>
            <td>s2</td>
            <td></td>
            <td></td>
            <td></td>
            <td>1</td>
            <td></td>
            <td></td>
        </tr>
        <tr>
            <td>1</td>
            <td></td>
            <td></td>
            <td></td>
            <td></td>
            <td>acc</td>
            <td></td>
            <td></td>
            <td></td>
        </tr>
        <tr>
            <td>2</td>
            <td>s2</td>
            <td>s3</td>
            <td></td>
            <td></td>
            <td></td>
            <td>5</td>
            <td>4</td>
            <td></td>
        </tr>
        <tr>
            <td>3</td>
            <td></td>
            <td></td>
            <td>r2</td>
            <td>r2</td>
            <td>r2</td>
            <td></td>
            <td></td>
            <td></td>
        </tr>
        <tr>
            <td>4</td>
            <td></td>
            <td></td>
            <td></td>
            <td>s10</td>
            <td></td>
            <td></td>
            <td></td>
            <td></td>
        </tr>
        <tr>
            <td>5</td>
            <td></td>
            <td></td>
            <td>s7</td>
            <td>r5</td>
            <td></td>
            <td></td>
            <td></td>
            <td>6</td>
        </tr>
        <tr>
            <td>6</td>
            <td></td>
            <td></td>
            <td></td>
            <td>r3</td>
            <td></td>
            <td></td>
            <td></td>
            <td></td>
        </tr>
        <tr>
            <td>7</td>
            <td>s2</td>
            <td>s3</td>
            <td></td>
            <td></td>
            <td></td>
            <td>8</td>
            <td></td>
            <td></td>
        </tr>
        <tr>
            <td>8</td>
            <td></td>
            <td></td>
            <td>s7</td>
            <td>r5</td>
            <td></td>
            <td></td>
            <td></td>
            <td>9</td>
        </tr>
        <tr>
            <td>9</td>
            <td></td>
            <td></td>
            <td></td>
            <td>r4</td>
            <td></td>
            <td></td>
            <td></td>
            <td></td>
        </tr>
        <tr>
            <td>10</td>
            <td></td>
            <td></td>
            <td>r1</td>
            <td>r1</td>
            <td>r1</td>
            <td></td>
            <td></td>
            <td></td>
        </tr>
    </tbody>
</table>
<p>不存在s/r冲突，也不存在r/r冲突，故文法G5'属于SLR文法。</p>
<h3 id="465"><a class="header" href="#465">4.6.5</a></h3>
<p>说明下面的文法</p>
<pre><code>S-&gt;AaAb|BbBa
A-&gt;ε
B-&gt;ε
</code></pre>
<p>是LL(1)的，但不是SLR(1)的。</p>
<h4 id="解答-3"><a class="header" href="#解答-3">解答</a></h4>
<ol>
<li>
<p>该文法是 LL(1) 的</p>
<p>见 4.4.3 节，p142 的判定标准</p>
</li>
<li>
<p>该文法不是 SLR(1) 的</p>
<pre><code> I_0
 
 S' -&gt; .S
 S -&gt; .AaAb
 S -&gt; .BbBa
 A -&gt; .
 B -&gt; .
</code></pre>
<p>由于 FOLLOW(A) = FOLLOW(B) = [a, b]，所以当 I_0 后输入为 a 或 b 时，就会发生规约冲突。</p>
</li>
</ol>
<h3 id="466"><a class="header" href="#466">4.6.6</a></h3>
<p>说明下面的文法</p>
<pre><code>S-&gt;SA|A
A-&gt;a
</code></pre>
<p>是SLR(1)的，但不是LL(1)的</p>
<h4 id="解答-4"><a class="header" href="#解答-4">解答</a></h4>
<ol>
<li>
<p>该文法不是 LL(1) 的</p>
<p><code>S -&gt; SA</code> 和 <code>S -&gt; A</code> 均能推导出以 a 开头的串，所以不是 LL(1) 的</p>
</li>
<li>
<p>该文法是 SLR(1) 的</p>
<p>该文法生成的语法分析表是没有冲突的</p>
</li>
</ol>
<h3 id="467"><a class="header" href="#467">4.6.7!!</a></h3>
<p>考虑按照下面的方式定义的文法族 G_n：</p>
<pre><code>S -&gt; A_i b_i         其中1&lt;=i&lt;=n
A_i-&gt; a_j A_j | a_j    其中1&lt;=i,j&lt;=n 且i&lt;&gt;n
</code></pre>
<p>说明：</p>
<ol>
<li>G_n有 2n^2-n 个产生式</li>
<li>G_n有 2^n+n^2+n 个 LR(0) 项集</li>
<li>G_n是 SLR(1) 的</li>
</ol>
<p>关于LR语法分析器的大小，这个分析结果说明了什么？</p>
<h3 id="468"><a class="header" href="#468">4.6.8!</a></h3>
<p>我们说单个项可以看做一个 NFA 的状态，而有效项的集合就是一个 DFA 的状态。对于练习4.2.1的文法 S-&gt;SS+|SS*|a</p>
<ol>
<li>根据“将项看作一个NFA的状态”部分中的规则，画出这个文法的有效的转换图（NFA）</li>
<li>将子集构造算法（算法3.20）应用于在（1）部分构造得到的NFA。得到的DFA和这个文法的LR(0)项集比有什么关系</li>
<li>！！ 说明在任何情况下，将子集构造算法应用于一个文法的有效项的NFA所得到的就是该文法的 LR(0) 项集</li>
</ol>
<h3 id="469"><a class="header" href="#469">4.6.9!</a></h3>
<p>下面是一个二义性的文法</p>
<pre><code>S-&gt;AS|b
A-&gt;SA|a
</code></pre>
<p>构造出这个文法的规范LR(0)项集族。如果我们试图为这个文法构造出一个LR语法分析表，必然会存在某些冲突动作。都有哪些冲突动作？假设我们使用这个语法分析表，并且在出现冲突时不确定地选择一个动作。给出输入abab时所有可能的动作序列</p>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="../../ch04/4.5/4.5.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="../../ch04/4.7/4.7.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="../../ch04/4.5/4.5.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="../../ch04/4.7/4.7.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>




        <script type="text/javascript">
            window.playground_copyable = true;
        </script>


        <script src="../../elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../searcher.js" type="text/javascript" charset="utf-8"></script>

        <script src="../../clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../book.js" type="text/javascript" charset="utf-8"></script>

        <!-- Custom JS scripts -->


    </body>
</html>
